#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/24 17:34
# ===========================================
#       题目名称： 37. 解数独
#       题目地址： https://leetcode.cn/problems/sudoku-solver/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
import itertools as _it
import time as _t


class Solution:
    """
        先实现3 * 3 里面的 然后再一次往左走
        118\109\113
    """

    def solveSudoku(self, board):
        """
            实现思路 ：

        """
        st = _t.time()
        boards = [board, ]  # 存放棋盘的列表
        const_piece = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]  # 常规棋子
        x, y = 0, 0  # 起始坐标      x 行 y 列
        while x < len(board) > y:
            if board[x][y] == ".":  # 判断当前可以落子
                temp_boards = []  # 创建临时棋盘用于保存现有的可能性
                for cur_board in boards:  # 遍历当前棋盘
                    # 判断当前这个点，可以洛那些子
                    cur_piece = const_piece.copy()  # 当前落子的地方可以落的子
                    # 3 * 3
                    x_33 = x - x % 3
                    y_33 = y - y % 3
                    for i in range(x_33, x_33 + 3):  # x 层
                        for j in range(y_33, y_33 + 3):  # y 列
                            if cur_board[i][j] == ".":
                                continue
                            if cur_board[i][j] in cur_piece:
                                cur_piece.remove(cur_board[i][j])
                    # x
                    for i in range(len(cur_board)):
                        if cur_board[i][y] == ".":
                            continue
                        if cur_board[i][y] in cur_piece:
                            cur_piece.remove(cur_board[i][y])

                    # y
                    for i in range(len(cur_board)):
                        if cur_board[x][i] == ".":
                            continue
                        if cur_board[x][i] in cur_piece:
                            cur_piece.remove(cur_board[x][i])

                    for piece in cur_piece:
                        temp_board = [item.copy() for item in cur_board].copy()
                        temp_board[x][y] = piece
                        temp_boards.append(temp_board)
                    print("x = %s, y = %s, piece = %s, len(temp_boards) = %s,消耗时间： %s" % (x, y, cur_piece, len(temp_boards), _t.time() - st))
                boards = temp_boards
            if y + 1 > len(board) - 1:
                x += 1
                y = 0
            else:
                y += 1
        # 恢复地址
        cur_board = boards[0]
        for x in range(len(board)):
            for y in range(len(board[x])):
                board[x][y] = cur_board[x][y]
        return cur_board

    def solveSudoku4(self, board):
        """
            时间超限
            实现思路 ：
            1、先通过3 * 3 来获取剩下可走的棋子
            2、将剩下可走的棋子进行排序 _it.permutations(剩下的棋子, 3 *3中可以走的点个数)
            3、然后将生成的排序 进行 x y 插入 找到符合规范的
        """
        st = _t.time()
        boards = [board, ]  # 存放棋盘的列表
        const_piece = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]  # 常规棋子
        x, y = 0, 0  # 起始坐标      x 行 y 列
        while x < len(board) > y:
            temp_boards = []
            for cur_board in boards:
                cur_piece = const_piece.copy()
                # 干掉3 * 3 的棋子
                for i in range(x, x + 3):  # x 层
                    for j in range(y, y + 3):  # y 列
                        # print(x, y, i, j, len(cur_board), len(cur_board[i]))
                        if cur_board[i][j] == ".":
                            continue
                        if cur_board[i][j] in cur_piece:
                            cur_piece.remove(cur_board[i][j])
                # 找到 3 * 3 剩余棋子的这些可能性
                pieces = []  # 判断第几位不能出现什么元素
                for i in range(x, x + 3):  # x 层
                    for j in range(y, y + 3):  # y 列
                        if cur_board[i][j] == ".":  # i， j 位置 x , y
                            # x
                            temp_cur_piece = cur_piece.copy()
                            for k in range(len(cur_board)):
                                if cur_board[k][j] == ".":
                                    continue
                                if cur_board[k][j] in temp_cur_piece:
                                    temp_cur_piece.remove(cur_board[k][j])
                            # y
                            for k in range(len(cur_board)):
                                if cur_board[i][k] == ".":
                                    continue
                                if cur_board[i][k] in temp_cur_piece:
                                    temp_cur_piece.remove(cur_board[i][k])
                            pieces.append(temp_cur_piece)
                elements = []
                for element in _it.permutations(cur_piece, len(cur_piece)):
                    # print(element)
                    is_chk_pass = True  # 是校验通过
                    # 1. 要求生成的数据 符合 x ,y
                    for i in range(len(element)):
                        if element[i] not in pieces[i]:  # 如果第i个元素出现不在这个范围的 下一个
                            is_chk_pass = False
                            break
                    if not is_chk_pass:
                        continue
                    stack = list(element)
                    temp_board = [item.copy() for item in cur_board]
                    for i in range(x, x + 3):  # x 层
                        for j in range(y, y + 3):  # y 列
                            if temp_board[i][j] == ".":
                                temp_board[i][j] = stack.pop(0)
                    if is_chk_pass:
                        temp_boards.append(temp_board)
                # print("x = %s , y = %s, len(boards) = %s, elements = %s" % (x, y, len(temp_boards), len(elements)))
            boards = temp_boards
            print("x = %s, y = %s, 消耗时长： %s" % (x, y, _t.time() - st))
            # 移动 3 * 3 的位置
            if y + 3 > len(board) - 1:
                x += 3
                y = 0
            else:
                y += 3
        # 恢复地址
        cur_board = boards[0]
        for x in range(len(board)):
            for y in range(len(board[x])):
                board[x][y] = cur_board[x][y]
        return cur_board

    def solveSudoku3(self, board):
        """
            实现思路 ：
            1、先通过3 * 3 来获取剩下可走的棋子
            2、将剩下可走的棋子进行排序 _it.permutations(剩下的棋子, 3 *3中可以走的点个数)
            3、然后将生成的排序 进行 x y 插入 找到符合规范的
        """
        boards = [board, ]  # 存放棋盘的列表
        const_piece = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]  # 常规棋子
        x, y = 0, 0  # 起始坐标      x 行 y 列
        while x < len(boards) > y:
            temp_boards = []
            for cur_board in boards:
                cur_piece = const_piece.copy()
                # 干掉3 * 3 的棋子
                for i in range(x, x + 3):  # x 层
                    for j in range(y, y + 3):  # y 列
                        if cur_board[i][j] == ".":
                            continue
                        if cur_board[i][j] in cur_piece:
                            cur_piece.remove(cur_board[i][j])
                # 找到 3 * 3 剩余棋子的这些可能性
                elements = []
                for element in _it.permutations(cur_piece, len(cur_piece)):
                    elements.append(element)
                # 遍历这些可能性 然后 进行 x , y 校验，通过存入临时棋盘
                for element in elements:
                    is_chk_pass = True
                    stack = list(element)
                    temp_board = [item.copy() for item in cur_board]
                    for i in range(x, x + 3):  # x 层
                        for j in range(y, y + 3):  # y 列
                            if temp_board[i][j] == ".":
                                temp_board[i][j] = stack.pop()
                    # x 判断
                    for i in range(x, x + 3):  # x 层
                        ct = temp_board[i]
                        st = list(set(temp_board[i]))
                        if len(ct) - ct.count(".") != len(st) - st.count("."):
                            is_chk_pass = False
                            break
                    # y 判断
                    if is_chk_pass:
                        for i in range(y, y + 3):  # y 列
                            temp_y_board = []
                            for j in range(len(temp_board)):
                                temp_y_board.append(temp_board[j][i])
                            ct = temp_y_board[i]
                            st = list(set(temp_y_board[i]))
                            if len(ct) - ct.count(".") != len(st) - st.count("."):
                                is_chk_pass = False
                                break

                    if is_chk_pass:
                        temp_boards.append(temp_board)
                print("x = %s , y = %s, len(boards) = %s, elements = %s" % (x, y, len(temp_boards), len(elements)))
            boards = temp_boards

            # 移动 3 * 3 的位置
            if y + 3 > len(boards) - 1:
                x += 3
                y = 0
            else:
                y += 3

    def solveSudoku2(self, board):
        """
            效率有问题
            Do not return anything, modify board in-place instead.
        """
        boards = [board, ]  # 存放棋盘的列表
        const_piece = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # 常规棋子
        for x in range(len(board)):
            for y in range(len(board[x])):
                if board[x][y] == ".":
                    continue
                temp_boards = []
                for cur_board in boards:
                    # 00    03      06      10      13      16
                    pieces = self.remove_piece(cur_board, const_piece.copy(), x - x % 3, y - y % 3, x, y)
                    for piece in pieces:
                        temp_board = cur_board.copy()
                        temp_board[x][y] = piece
                        temp_boards.append(temp_board)
                boards = temp_boards
                print("x = %s , y = %s, len(boards) = %s" % (x, y, len(boards)))

    def remove_piece(self, cur_board, cur_piece, x, y, cur_x, cur_y):
        """
            移除棋子
            @param cur_board {List[List]} 当前棋盘
            @param cur_piece {List} 当前棋子
            @param x {int} 起始坐标 x
            @param y {int} 起始坐标 y
            @param cur_x {int} 当前坐标 x
            @param cur_y {int} 当前坐标 y
        """
        # 3 * 3
        for i in range(x, x + 3):  # x 层
            for j in range(y, y + 3):  # y 列
                if cur_board[i][j] == ".":
                    continue
                if cur_board[i][j] in cur_piece:
                    cur_piece.remove(cur_board[i][j])
        # x
        for i in range(len(cur_board)):
            if cur_board[i][cur_y] == ".":
                continue
            if cur_board[i][cur_y] in cur_piece:
                cur_piece.remove(cur_board[i][cur_y])

        # y
        for i in range(len(cur_board)):
            if cur_board[cur_x][i] == ".":
                continue
            if cur_board[cur_x][i] in cur_piece:
                cur_piece.remove(cur_board[cur_x][i])

        return cur_piece


if __name__ == '__main__':
    s = Solution()
    print(s.solveSudoku(board=[
        ["5", "3", ".", ".", "7", ".", ".", ".", "."],
        ["6", ".", ".", "1", "9", "5", ".", ".", "."],
        [".", "9", "8", ".", ".", ".", ".", "6", "."],
        ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
        ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
        ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
        [".", "6", ".", ".", ".", ".", "2", "8", "."],
        [".", ".", ".", "4", "1", "9", ".", ".", "5"],
        [".", ".", ".", ".", "8", ".", ".", "7", "9"]]))
    print(s.solveSudoku(board=[
        [".", ".", "9", "7", "4", "8", ".", ".", "."],
        ["7", ".", ".", ".", ".", ".", ".", ".", "."],
        [".", "2", ".", "1", ".", "9", ".", ".", "."],
        [".", ".", "7", ".", ".", ".", "2", "4", "."],
        [".", "6", "4", ".", "1", ".", "5", "9", "."],
        [".", "9", "8", ".", ".", ".", "3", ".", "."],
        [".", ".", ".", "8", ".", "3", ".", "2", "."],
        [".", ".", ".", ".", ".", ".", ".", ".", "6"],
        [".", ".", ".", "2", "7", "5", "9", ".", "."]]))
